// 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

// 返回 s 所有可能的分割方案。

// 示例:

// 输入: "aab"
// 输出:
// [
//   ["aa","b"],
//   ["a","a","b"]
// ]

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res{};
        vector<string> out{};
        func(s, 0, out, res);
        return res;
    }
    void func(string s, int start, vector<string>& out, vector<vector<string>>& res) {
        if (start == s.size()) {
            res.push_back(out);
            return;
        }
        for (int i = start; i < s.size(); ++i) {
            if (!isPalindrome(s, start, i)) continue;
            out.push_back(s.substr(start, i-start+1));
            func(s, i+1, out, res);
            out.pop_back();
        }
    }
    bool isPalindrome(string s, int start, int end) { // 判断是否是回文串
        while (start < end) {
            if (s[start] != s[end]) return false;
            ++start;
            --end;
        }
        return true;
    }
};

/* 回溯 + 动态规划预处理
使用搜索 + 回溯的方法枚举所有可能的分割方法并进行判断。
*/
class Solution {
public:
    vector<vector<string>> partition(string s) {
        n = s.size();
        dp.assign(n, vector<bool>(n, true));

        for (int i{n - 1}; i >= 0; --i) {
            for (int j{i + 1}; j < n; ++j) {
                dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];
            }
        }

        dfs(s, 0);
        return ret;
    }
    void dfs(const string& s, int i) {
        if (i == n) {
            ret.push_back(temp);
            return;
        }
        for (int j{i}; j < n; ++j) {
            if (dp[i][j]) {
                temp.push_back(s.substr(i, j - i + 1));
                dfs(s, j + 1);
                temp.pop_back();
            }
        }
    }
private:
    vector<vector<bool>> dp{}; // dp[i][j]表示s(i, j)是回文串
    vector<vector<string>> ret{};
    vector<string> temp{};
    int n{0};
};

/* 回溯 + 记忆化搜索
*/
class Solution {
public:
    vector<vector<string>> partition(string s) {
        n = s.size();
        dp.assign(n, vector<int>(n));
        dfs(s, 0);
        return ret;
    }
    void dfs(const string& s, int i) {
        if (i == n) {
            ret.push_back(temp);
            return;
        }
        for (int j{i}; j < n; ++j) {
            if (isPalindrome(s, i, j) == 1) {
                temp.push_back(s.substr(i, j - i + 1));
                dfs(s, j + 1);
                temp.pop_back();
            }
        }
    }
    // 记忆化搜索中，dp[i][j] == 0 表示未搜索，1表示回文串，-1表示不是回文串
    int isPalindrome(const string& s, int i, int j) {
        if (dp[i][j]) {
            return dp[i][j];
        }
        if (i >= j) {
            return dp[i][j] = 1;
        }
        return dp[i][j] = (s[i] == s[j] ? isPalindrome(s, i + 1, j - 1) : -1);
    }
private:
    vector<vector<int>> dp{};
    vector<vector<string>> ret{};
    vector<string> temp{};
    int n{};
};